﻿if (!Array.prototype.forEach) {//例举数组中的每个元素，运行作为参数的函数。
    Array.prototype.forEach = function (fun /*, thisp*/) {
        var len = this.length;
        if (typeof fun != "function")
            throw new TypeError();

        var thisp = arguments[1];
        for (var i = 0; i < len; i++) {
            if (i in this)
                fun.call(thisp, this[i], i, this);
        }
    };
}
//function rectCompare
var lib = {};
lib.removeEleFromArray = function (_array, _ele) {
    for (var i = 0; i < _array.length; i++) {
        if (_array[i] == _ele) {
            _array.splice(i,1);
            break;
        }
    }
};

lib.pushArray = function (_container, _children) {
    for (var i = 0; i < _children.length; i++) {
        _container.push(_children[i]);
    }
};
lib.mergeArray = function (_arrayA, _arrayB) {//merge two arraies
    var arrayA = copyArray(_arrayA);
    arrayB = copyArray(_arrayB);
    var arrayC = [];

    do {
        if (arrayA.length == 0 && arrayB.length != 0) {
            arrayC.push(arrayB[0]);
            arrayB.splice(0, 1);
        } else if (arrayA.length != 0 && arrayB.length == 0) {
            arrayC.push(arrayA[0]);
            arrayA.splice(0, 1);
        } else if (arrayA[0] > arrayB[0]) {
            arrayC.push(arrayB[0]);
            arrayB.splice(0, 1);
        } else if (arrayA[0] == arrayB[0]) {
            arrayC.push(arrayB[0]);
            arrayA.splice(0, 1);
            arrayB.splice(0, 1);
        } else {
            arrayC.push(arrayA[0]);
            arrayA.splice(0, 1);
        }
    } while (arrayA.length != 0 || arrayB.length != 0)
    return arrayC;
};

lib.getLastBottom = function (p_arr, p_item) {
    var t_top = 0;
    for (var i = 0, t; t = p_arr[i]; i++) {
        var tmp = t.clientTop + t.clientHeight;
        var xs = lib.mergeArray([t.clientTop, t.clientTop + t.clientWidth], [p_item.clientTop, p_item.clientTop + p_item.clientWidth]);
        if (lib.isRectsCrossOnX(t,p_item) && tmp <= p_item.clientTop && tmp > t_top) {
            t_top = tmp;
        }
    }
    return t_top;
};

lib.interceptArray = function (p_arr, p_min, p_max, p_fun) {
    var a = lib.getIndex(p_arr, p_min, p_fun);
    var b = lib.getIndex(p_arr, p_max, p_fun);
    var tmp = [];
    for (var i = a; i < b; i++) {
        tmp.push(p_arr[i]);
    }
    return tmp;
};

lib.getIndex = function (p_arr, p_i, p_fun) {
    var a = 0;
    var b = p_arr.length - 1;
    while (true) {
        if (p_fun(p_i, p_arr[a]) < 0) {
            return a;
        } else if (p_fun(p_i, p_arr[parseInt((a + b) / 2)]) < 0) {
            b = parseInt((a + b) / 2);
            if (b - a <= 1) {
                return a + 1;
            }
        } else if (p_fun(p_i, p_arr[b]) < 0) {
            a = parseInt((a + b) / 2);
            if (b - a <= 1) {
                return a + 1;
            }
        } else {
            return b + 1;
        }
    }
};

lib.getAccordantVir = function (virDoms, realDom) {//为realDom找到大小合适的空隙.
    var a = virDoms.length;
    for (var i = 0, t; t = virDoms[i]; i++) {
        if (t.clientWidth >= 1 * realDom.clientWidth && t.clientHeight >= 1 * realDom.clientHeight) {
            return t;
        }
    }
};

lib.getAccordantVirs = function (virDoms, realDom) {//working
    var a = virDoms.length;
    for (var i = 0, t; t = virDoms[i]; i++) {
        if (t.clientWidth >= 1 * realDom.clientWidth && t.clientHeight >= 1 * realDom.clientHeight) {
            return t;
        } else {
            var implement = t.createComplement(realDom);
            if (implement.complementsInVirDom.length > 0) {
                return t;
            }
        }
    }
};

/*
* @function find an accordant gap whose size is larger or equal to 'realDom',and modify 'emptyDoms', 'fromDoms'.
* @param {Array} emptyDoms all the gaps created.
* @fromDoms {Array} fromDoms all the divs to be inserted.
* @realDom {object} the div to be inserted at present.
*/

lib.fillDom = function (emptyDoms, fromDoms, realDom) {
    for (var i = 0, t; t = emptyDoms[i]; i++) {
        if (t.clientWidth >= 1 * realDom.clientWidth && t.clientHeight >= 1 * realDom.clientHeight) {
            realDom.clientLeft = t.clientLeft;
            realDom.clientTop = t.clientTop;
            realDom.ele.style.left = t.clientLeft + "px";
            realDom.ele.style.top = t.clientTop + "px";
            realDom.ele.style.zIndex = "9";
            realDom.ele.style.visibility = "";
            emptyDoms.splice(i, 1); //删除这个匹配的空隙
            for (var k = 0; k < fromDoms.length; k++) {//将补集添加上去.
                if (fromDoms[k] === realDom) {
                    fromDoms.splice(k, 1);
                    break;
                }
            }
            var implements = t.createComplement(realDom).complementsInVirDom;
            for (var k = 0; k < implements.length; k++) {//将补集一一添加上去.
                emptyDoms.splice(t + k, 0, implements[k]);
            }
        }
    }
};

/*  A
--------------
|   |   |    |
--------------
|   |    |   |
|   |    |   |
--------------
|   |    |   |
|   |    |   |
--------------
*/
lib.getARecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    for (var i = 0; i < Xs.length - 1; i++) {
        for (var j = 0; j < Ys.length - 1; j++) {
            var l = Xs[i];
            var t = Ys[j];
            var w = Xs[i + 1] - Xs[i];
            var h = Ys[j + 1] - Ys[j];
            var isInSRect = (p_SRect.clientLeft <= l && l + w <= p_SRect.clientLeft + p_SRect.clientWidth && p_SRect.clientTop <= t && t + h <= p_SRect.clientTop + p_SRect.clientHeight);
            if (!isInSRect) {
                complements.push(new VirtualDom(l, t, w, h));
            }
        }
    }
    return complements;
};
/*  B
--------------
|            |
--------------
|   |    |   |
|   |    |   |
--------------
|            |
|            |
--------------
*/
lib.getBRecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    for (var j = 0; j < Ys.length - 1; j++) {
        var t = Ys[j];
        var h = Ys[j + 1] - Ys[j];
        if (t < p_SRect.clientTop || t >= p_SRect.clientTop + p_SRect.clientHeight) {
            var l = p_LRect.clientLeft;
            var w = p_LRect.clientWidth;
            complements.push(new VirtualDom(l, t, w, h))
        } else {
            for (var i = 0; i < Xs.length - 1; i++) {
                var l = Xs[i];
                var w = Xs[i + 1] - Xs[i];
                var isInSRect = (p_SRect.clientLeft <= l && l + w <= p_SRect.clientLeft + p_SRect.clientWidth && p_SRect.clientTop <= t && t + h <= p_SRect.clientTop + p_SRect.clientHeight);
                if (!isInSRect) {
                    complements.push(new VirtualDom(l, t, w, h));
                }
            }
        }
    }
    return complements;
};
lib.getCRecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    for (var i = 0; i < Xs.length - 1; i++) {
        var l = Xs[i];
        var w = Xs[i + 1] - Xs[i];
        if (l < p_SRect.clientLeft || t >= p_SRect.clientLeft + p_SRect.clientWidth) {
            var t = p_LRect.clientTop;
            var h = p_LRect.clientHeight;
            complements.push(new VirtualDom(l, t, w, h))
        } else {
            for (var j = 0; j < Ys.length - 1; j++) {
                var t = Ys[j];
                var h = Ys[j + 1] - Ys[j];
                var isInSRect = (p_SRect.clientLeft <= l && l + w <= p_SRect.clientLeft + p_SRect.clientWidth && p_SRect.clientTop <= t && t + h <= p_SRect.clientTop + p_SRect.clientHeight);
                if (!isInSRect) {
                    complements.push(new VirtualDom(l, t, w, h));
                }
            }
        }
    }
    return complements;
};
lib.getDRecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    if (p_SRect.clientTop > p_LRect.clientTop) {
        var t = Ys[0];
        var h = Ys[1] - Ys[0];
        var l = p_LRect.clientLeft;
        var w = p_LRect.clientWidth;
        complements.push(new VirtualDom(l, t, w, h));
    } 

    for (var i = 0; i < Xs.length - 1; i++) {
        var l = Xs[i];
        var w = Xs[i + 1] - Xs[i];
        if (Xs[i] == p_SRect.clientLeft) {
            var t = p_SRect.clientTop + p_SRect.clientHeight;
            var h = p_LRect.clientTop + p_LRect.clientHeight - (p_SRect.clientTop + p_SRect.clientHeight);
        } else {
            var t = p_SRect.clientTop;
            var h = p_LRect.clientTop + p_LRect.clientHeight - p_SRect.clientTop;
        }
        if (w * h != 0)  complements.push(new VirtualDom(l, t, w, h));
    }
    return complements;
};
lib.getERecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    if (p_SRect.clientLeft > p_LRect.clientLeft) {
        var l = Xs[0];
        var w = Xs[1] - Xs[0];
        var t = p_LRect.clientTop;
        var h = p_LRect.clientHeight;
        complements.push(new VirtualDom(l, t, w, h));
    }

    for (var j = 0; j < Ys.length - 1; j++) {
        var t = Ys[j];
        var h = Ys[j+1] - Ys[j];
        if (Ys[j] == p_SRect.clientTop) {
            var l = p_SRect.clientLeft + p_SRect.clientWidth;
            var w = p_LRect.clientLeft + p_LRect.clientWidth - (p_SRect.clientLeft + p_SRect.clientWidth);
        } else {
            var l = p_SRect.clientLeft;
            var w = p_LRect.clientLeft + p_LRect.clientWidth - p_SRect.clientLeft;
        }
        if (w * h != 0) complements.push(new VirtualDom(l, t, w, h));
    }
    return complements;
};
lib.getFRecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    if (p_LRect.clientLeft + p_LRect.clientWidth > p_SRect.clientLeft + p_SRect.clientWidth) {
        var l = p_SRect.clientLeft + p_SRect.clientWidth;
        var w = p_LRect.clientLeft + p_LRect.clientWidth - (p_SRect.clientLeft + p_SRect.clientWidth);
        var t = p_LRect.clientTop;
        var h = p_LRect.clientHeight;
        complements.push(new VirtualDom(l, t, w, h));
    }

    for (var j = 0; j < Ys.length - 1; j++) {
        var t = Ys[j];
        var h = Ys[j + 1] - Ys[j];
        if (Ys[j] == p_SRect.clientTop) {
            var l = p_LRect.clientLeft;
            var w = p_SRect.clientLeft - p_LRect.clientLeft;
        } else {
            var l = p_LRect.clientLeft;
            var w = p_SRect.clientLeft + p_SRect.clientWidth - p_LRect.clientLeft;
        }
        if( w*h != 0) complements.push(new VirtualDom(l, t, w, h));
    }
    return complements;
};
lib.getGRecComp = function (p_LRect, p_SRect) {
    var tmpA = [p_LRect.clientLeft, p_LRect.clientLeft + p_LRect.clientWidth];
    var tmpB = [p_SRect.clientLeft, p_SRect.clientLeft + p_SRect.clientWidth];
    var Xs = lib.mergeArray(tmpA, tmpB);
    var Ys = lib.mergeArray([p_LRect.clientTop, p_LRect.clientTop + p_LRect.clientHeight], [p_SRect.clientTop, p_SRect.clientTop + p_SRect.clientHeight]);
    var complements = [];
    if (p_LRect.clientTop + p_LRect.clientHeight > p_SRect.clientTop + p_SRect.clientHeight) {
        var t = p_SRect.clientTop + p_SRect.clientHeight;
        var h = p_LRect.clientTop + p_LRect.clientHeight - (p_SRect.clientTop + p_SRect.clientHeight);
        var l = p_LRect.clientLeft;
        var w = p_LRect.clientWidth;
        complements.push(new VirtualDom(l, t, w, h));
    }
    for (var i = 0; i < Xs.length - 1; i++) {
        var l = Xs[i];
        var w = Xs[i + 1] - Xs[i];
        if (Xs[i] == p_SRect.clientLeft) {
            var t = p_LRect.clientTop;
            var h = p_SRect.clientTop - p_LRect.clientTop;
        } else {
            var t = p_LRect.clientTop;
            var h = p_SRect.clientTop + p_SRect.clientHeight - p_LRect.clientTop;
        }
        if (w * h != 0) complements.push(new VirtualDom(l, t, w, h));
    }
    return complements;
};

lib.boxup = function (p_receiver, p_rect) {//将单个元素或多个元素放入数组容器。
    function tmpFun(a, b) {
        if (a == undefined || b==undefined) return 0;
        if (a.clientTop < b.clientTop) return -1;
        if (a.clientTop == b.clientTop && a.clientLeft < b.clientLeft) {
            return -1;
        }
        return 1;
    }
    if (p_rect.length == undefined) {
        lib.quickInsertToSequen(p_receiver, p_rect, tmpFun);
    } else {
        for (var i = 0, t; t = p_rect[i]; i++) {
            lib.quickInsertToSequen(p_receiver, t, tmpFun);
        }
    }
    return p_receiver;
};

lib.boxup_bottom = function (p_receiver, p_rect) {//将单个元素或多个元素放入数组容器。
    function tmpFun(a, b) {
        if (a == undefined || b == undefined) return 0;
        var x1 = a.clientLeft,y1=a.clientTop+a.clientHeight,x2 = b.clientLeft,y2=b.clientTop+b.clientHeight;
        if (y1 < y2) return -1;
        if (y1 == y2 && x1 < x2) {
            return -1;
        }
        return 1;
    }
    if (p_rect.length == undefined) {
        lib.quickInsertToSequen(p_receiver, p_rect, tmpFun);
    } else {
        for (var i = 0, t; t = p_rect[i]; i++) {
            lib.quickInsertToSequen(p_receiver, t, tmpFun);
        }
    }
    return p_receiver;
};

lib.isRectBlanck = function (p_r_rects, rect) {
    for (var i = 0, t; t = p_r_rects[i]; i++) {//如果不和任何实rect相交，则说明此rect可以被虚rect完全覆盖。
        var Xarr = [t.clientLeft, t.clientLeft + t.clientWidth, rect.clientLeft, rect.clientLeft + rect.clientWidth].sort(function (a, b) { return a - b; });
        var Xdif = Xarr[3] - Xarr[0];
        var Yarr = [t.clientTop, t.clientTop + t.clientHeight, rect.clientTop, rect.clientTop + rect.clientHeight].sort(function (a, b) { return a - b; });
        var Ydif = Yarr[3] - Yarr[0];
        if ((Xdif < t.clientWidth + rect.clientWidth) && (Ydif < t.clientHeight + rect.clientHeight)) {//如果在x方向交汇或在y方向交汇.
            return false;
        }
    }
    return true; //不和任何实rect相交.
}
//获取两个矩形的相交部分形成的矩形．
// @param {VirtualDom} virDom    :a rectangle
lib.getIntersection = function (a, b) {
    var Xarr = [a.clientLeft, a.clientLeft + a.clientWidth, b.clientLeft, b.clientLeft + b.clientWidth].sort(function (p_a, p_b) {
        return p_a - p_b;
    });
    var Xdif = Xarr[3] - Xarr[0];
    var Yarr = [a.clientTop, a.clientTop + a.clientHeight, b.clientTop, b.clientTop + b.clientHeight].sort(function (p_a, p_b) {
        return p_a - p_b;
    });
    var Ydif = Yarr[3] - Yarr[0];
    if ((Xdif < a.clientWidth + b.clientWidth) && (Ydif < a.clientHeight + b.clientHeight)) {//如果在x方向交汇或在y方向交汇.
        var intersection = new VirtualDom(Xarr[1], Yarr[1], Xarr[2] - Xarr[1], Yarr[2] - Yarr[1]);
        return intersection;
    }
    return undefined;
};

lib.getRectsIntersect = function (p_r_rects, rect) {//获取所有和rect相交的虚rect.
    var intersection = [];
    for (var i = 0, t; t = p_r_rects[i]; i++) {//如果不和任何实rect相交，则说明此rect可以被虚rect完全覆盖。
        var Xarr = [t.clientLeft, t.clientLeft + t.clientWidth, rect.clientLeft, rect.clientLeft + rect.clientWidth].sort(function (p_a, p_b) {
            return p_a - p_b;
        });
        var Xdif = Xarr[3] - Xarr[0];
        var Yarr = [t.clientTop, t.clientTop + t.clientHeight, rect.clientTop, rect.clientTop + rect.clientHeight].sort(function (p_a, p_b) {
            return p_a - p_b;
        });
        var Ydif = Yarr[3] - Yarr[0];
        if ((Xdif < t.clientWidth + rect.clientWidth) && (Ydif < t.clientHeight + rect.clientHeight)) {//如果在x方向交汇或在y方向交汇.
            if (isNaN(Xdif) || isNaN(t.clientWidth) || isNaN(rect.clientWidth) || isNaN(Ydif) || isNaN(t.clientHeight) || isNaN(rect.clientHeight)) {
                alert("is not a number");
            }
            intersection.push(t);
        }
    }
    return intersection;
};

lib.arrayRemoveItem = function (p_array, p_item) {
    for (var i = 0; i < p_array.length; i++) {
        if (p_array[i] == p_item) {
            p_array.splice(i, 1);
        }
    }
};

lib.isBeyondRange = function (p_LRect, p_SRect) {//判断小长方形是否溢出大长方形.
    if (p_LRect.clientLeft <= p_SRect.clientLeft && p_SRect.clientLeft + p_SRect.clientWidth <= p_LRect.clientLeft + p_LRect.clientWidth
       && p_LRect.clientTop <= p_SRect.clientTop && p_SRect.clientTop + p_SRect.clientHeight <= p_LRect.clientLeft + p_LRect.clientHeight) {
        return false;
    }
    return true;
};

lib.quickInsertToSequen = function (p_arr, p_i, p_fun) {
    var a = 0;
    var b = p_arr.length - 1;
    while (true) {
        if (p_fun(p_i, p_arr[a]) < 0) {
            p_arr.splice(a, 0, p_i);
            break;
        } else if (p_fun(p_i, p_arr[parseInt((a + b) / 2)]) < 0) {
            b = parseInt((a + b) / 2);
            if (b - a <= 1) {
                p_arr.splice(a + 1, 0, p_i);
                break;
            }
        } else if (p_fun(p_i, p_arr[b]) < 0) {
            a = parseInt((a + b) / 2);
            if (b - a <= 1) {
                p_arr.splice(a + 1, 0, p_i);
                break;
            }
        } else {
            p_arr.splice(b + 1, 0, p_i);
            break;
        }
    }
};

lib.isRectsCrossOnX = function (p_rectA, p_rectB) {//判断两个长方形在x轴方向上是否相交.
    var xs = lib.mergeArray([p_rectA.clientLeft, p_rectA.clientLeft + p_rectA.clientWidth], [p_rectB.clientLeft, p_rectB.clientLeft + p_rectB.clientWidth]);
    if (xs[xs.length - 1] - xs[0] < p_rectA.clientWidth + p_rectB.clientWidth) {
        return true;
    }
    return false;
};
